class Node:
    """节点类：由两部分组成，数据区域（元素区域） 和指针区域"""

    def __init__(self, data, prev_node=None, next_node=None):
        self.data = data
        self.next = next_node  # 链接到后一个节点
        self.prev = prev_node  # 链接到前一个节点


class DubleLink:
    """双向链表"""

    def __init__(self):
        self.head = None  # 空的单向链表，一开始没有头部节点
        self._length = 0  # 空的列表，代表数据的个数或者链表的长度 私有定制

    def length(self):  # 返回链表长度
        return self._length

    def is_empty(self):  # 判断链表是否为空
        return self._length == 0

    def add(self, new_data):
        """
        往头部插入新节点
        :param new_data:
        :return:
        """
        node = Node(new_data)
        if self.is_empty():
            self.head = node  # 当前链表为空
        else:
            # 让链表中原来的head节点的prev指向新建的节点node
            self.head.prev = node
            # 正在插入的节点等于原来的节点
            node.next = self.head
            # 把新建的node节点作为头节点
            self.head = node
        self._length += 1

    def insert(self, new_data, pos):
        """
        把新的数据插入到指定位置
        :param new_data:
        :param pos:从头系欸但开始的逻辑下标
        :return:
        """
        if pos <= 0:
            self.add(new_data)
        elif pos >= self._length:  # 考虑尾部
            self.append(new_data)
        else:  # 中间
            node = Node(new_data)
            # 找到要插入的位置
            cur = self.head
            while pos - 1:
                cur = cur.next
                pos -= 1
            # 新建的node节点的prev指向原来前一个节点的next节点
            node.prev = cur
            # 新建node 节点的next指向原来前一个节点的next节点
            node.next = cur.next
            # 原来前一个节点的next节点的prev指向新建的node节点
            cur.next.prev = node
            # 原来前一个节点的next执行当前新建的node节点
            cur.next = node

            self._length += 1

    def append(self, new_data):
        """
        尾部添加
        :param new_data:
        :return:
        """
        node = Node(new_data)
        if self.is_empty():  # 原来的链表就是空的，那么就是添加到第一个
            return self.add(new_data)
        else:  # 原来链表中不是空的,从头节点 开始 依次往下找，一直到最后一个节点
            cur = self.head
            while cur.next:
                cur = cur.next
            # cur就是最后一个节点
            # 新建节点node的prev指向原来的尾节点
            node.prev = cur
            cur.next = node
            self._length += 1

    def remove(self, data):
        # 找到 ，你要删除的这个数据的前一个节点
        cur = self.head
        while cur:
            if cur.data == data:  # 找到了要删除的节点
                if cur == self.head:  # 当前要删除的节点就是头节点
                    self.head = cur.next
                else:
                    cur.prev.next = cur.next
                if cur.next:
                    cur.next.prev = cur.prev
                self._length -= 1
                return True  # 找到返回一个True
            else:
                # 没有找到，继续向下遍历
                cur = cur.next
        return False  # 没有找打数据

    def remove_pos(self, pos):
        pass
        # # 按照指定位置删除指定位置的节点
        # if pos <= 0:  # 删除头节点
        #     self.head = self.head.next
        # elif pos >= self._length:  # 考虑尾部 删除尾节点
        #     cur = self.head
        #     pre = None
        #     while cur.next:  # cur.next为空就是最后一个节点
        #         pre = cur
        #         cur = cur.next
        #     # cur就是最后一个节点
        #     pre.next = None  # 这就是删除最后一个节点
        # else:  # 删除中间的某个节点
        #     # 找到要删除的前一个节点
        #     pre = self.head
        #     while pos - 1:
        #         pre = pre.next
        #         pos -= 1
        #     cur = pre.next
        #     pre.next = cur.next
        # self._length -= 1
        # return True

    def modify(self, pos, new_data):  # 修改
        if 0 <= pos < self._length:  # 没有越界
            cur = self.head
            while pos:  # 找到要修改的
                cur = cur.next
                pos -= 1
            cur.data = new_data
        else:  # 下标越界
            print('输入的下标有误！')

    def search(self, data):  # 查询
        cur = self.head
        while cur:
            if cur.data == data:
                return True
            cur = cur.next
        return False

    def to_list(self):
        """
        把当前链表转换为列表
        :return:
        """
        res = []
        cur = self.head
        while cur:
            res.append(cur.data)
            cur = cur.next  # 当前节点继续指向下一个节点
        return res


if __name__ == '__main__':
    sll = DubleLink()
    sll.add(11)
    sll.append(44)
    sll.add(80)
    sll.insert(99, 2)
    print(sll.search(99))
    print(sll.search(22))
    sll.modify(1, 100)
    sll.modify(0, 100)
    print(sll.to_list())
